home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / SCHEME / GNU / SCM4E1 / !Scm / slib / queue < prev    next >
Text File  |  1993-03-05  |  2KB  |  72 lines
  1. ; queue.scm  Queues/Stacks for Scheme
  2. ; Written by Andrew Wilcox (awilcox@astro.psu.edu) on April 1, 1992.
  3. ; This code is in the public domain.
  4.  
  5. (require 'record)
  6.  
  7. ; Elements in a queue are stored in a list.  The last pair in the list
  8. ; is stored in the queue type so that datums can be added in constant
  9. ; time.
  10.  
  11. (define queue:record-type
  12.   (make-record-type "queue" '(first-pair last-pair)))
  13. (define make-queue
  14.   (let ((construct-queue (record-constructor queue:record-type)))
  15.     (lambda ()
  16.       (construct-queue '() '()))))
  17.  
  18. (define queue? (record-predicate queue:record-type))
  19.  
  20. (define queue:first-pair (record-accessor queue:record-type
  21.                       'first-pair))
  22. (define queue:set-first-pair! (record-modifier queue:record-type
  23.                            'first-pair))
  24. (define queue:last-pair (record-accessor queue:record-type
  25.                      'last-pair))
  26. (define queue:set-last-pair! (record-modifier queue:record-type
  27.                           'last-pair))
  28.  
  29. (define (queue-empty? q)
  30.   (null? (queue:first-pair q)))
  31.  
  32. (define (queue-front q)
  33.   (let ((first-pair (queue:first-pair q)))
  34.     (if (null? first-pair)
  35.     (slib:error "queue is empty" q))
  36.     (car first-pair)))
  37.  
  38. (define (queue-rear q)
  39.   (let ((last-pair (queue:last-pair q)))
  40.     (if (null? last-pair)
  41.     (slib:error "queue is empty" q))
  42.     (car last-pair)))
  43.  
  44. (define (queue-push! q datum)
  45.   (let* ((old-first-pair (queue:first-pair q))
  46.      (new-first-pair (cons datum old-first-pair)))
  47.     (queue:set-first-pair! q new-first-pair)
  48.     (if (null? old-first-pair)
  49.     (queue:set-last-pair! q new-first-pair)))
  50.   q)
  51.     
  52. (define (enqueue! q datum)
  53.   (let ((new-pair (cons datum '())))
  54.     (cond ((null? (queue:first-pair q))
  55.        (queue:set-first-pair! q new-pair))
  56.       (else
  57.        (set-cdr! (queue:last-pair q) new-pair)))
  58.     (queue:set-last-pair! q new-pair))
  59.   q)
  60.  
  61. (define (dequeue! q)
  62.   (let ((first-pair (queue:first-pair q)))
  63.     (if (null? first-pair)
  64.     (slib:error "queue is empty" q))
  65.     (let ((first-cdr (cdr first-pair)))
  66.       (queue:set-first-pair! q first-cdr)
  67.       (if (null? first-cdr)
  68.       (queue:set-last-pair! q '()))
  69.       (car first-pair))))
  70.  
  71. (define queue-pop! dequeue!)
  72.